package com.leetcode;


import com.leetcode.support.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 剑指 Offer II 046. 二叉树的右侧视图
 *
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 *
 */
public class LeetCodeOffer46 {

	public static void main(String[] arg0) {
		// 没有测试用例，直接再网站上提交通过了
	}

	public static List<Integer> rightSideView(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}

		Map<Integer, Integer> rightmostValueAtDepth = new HashMap<>(); // 最后边的值所在的深度
		int max_depth = -1; // 最大深度，一开始记为 -1

		// 两个队列，一个记当前深度的节点，一个记深度
		Deque<TreeNode> nodeStack = new ArrayDeque<>();
		Deque<Integer> depthStack = new ArrayDeque<>();
		nodeStack.push(root);
		depthStack.push(0);

		while (!nodeStack.isEmpty()) {
			TreeNode node = nodeStack.pop();
			int depth = depthStack.pop();

			if (node != null) {
				// 维护二叉树的最大深度
				max_depth = Math.max(max_depth, depth);

				// 如果不存在对应深度的节点我们才插入，因为 nodeStack 会一直循环到不为空，
				// 所有只要最右边的节点值，不能让左边的节点值替换了当前深度的右视图值
				if (!rightmostValueAtDepth.containsKey(depth)) {
					rightmostValueAtDepth.put(depth, node.val);
				}

				if (node.left != null) {
					nodeStack.push(node.left);
					depthStack.push(depth + 1);
				}
				if (node.right != null) {
					nodeStack.push(node.right);
					depthStack.push(depth + 1);
				}
			}
		}

		for (int depth = 0; depth <= max_depth; depth++) {
			res.add(rightmostValueAtDepth.get(depth));
		}

		return res;
	}

}
